🎒 0/1 Knapsack with Branch and Bound - Jack's Treasure Hunt

Help Jack maximize the value of treasures within his backpack's weight limit

🧑‍💻 Jack's Treasure Hunt Challenge

🎯 The Mission:

Help Jack maximize the total value of treasures by selecting items with the best value-to-weight ratio within his backpack's weight capacity using Branch and Bound.

📋 Requirements:

  • Select items to maximize total value
  • Respect backpack weight capacity v
  • Each item has weight and value
  • Output maximum value, rounded to two decimal places

Input/Output Specifications

  • Input: u (number of items), v (backpack capacity), u weights, u values
  • Output: Maximum value (float, two decimal places)
  • Constraints: 1 ≤ u ≤ 100, 1 ≤ v ≤ 1000, 1 ≤ weight[i] ≤ 100, 1 ≤ value[i] ≤ 1000

Example 1: u=2, v=10, weights=[5,5], values=[50,60]

Items:

W:5, V:50
W:5, V:60

Output: 110.00

Example 2: u=3, v=6, weights=[1,1,3], values=[10,20,40]

Items:

W:1, V:10
W:1, V:20
W:3, V:40

Output: 70.00

⚡ Branch and Bound Explained

How Branch and Bound Works for Knapsack

  1. Sort Items: Order items by value-to-weight ratio in descending order
  2. Bound Function: Calculate upper bound for a node by adding current profit and maximum possible profit from remaining items
  3. Explore Nodes: Use a queue to explore nodes (include/exclude item), pruning branches with bound ≤ current max profit
  4. Track Maximum: Update max profit when a valid solution is found

Example Decision Tree (u=2, v=5, weights=[2,3], values=[40,50])

Root: Profit=0, Weight=0, Bound=90
Include Item 1 (W:2, V:40): Profit=40, Weight=2, Bound=90
Exclude Item 1: Profit=0, Weight=0, Bound=50

Output: 50.00 (select item 2)

Time Complexity

O(2^u)

Worst case, but pruning reduces nodes explored

Space Complexity

O(u)

For queue and recursion stack

Why Branch and Bound?

  • ✅ Optimizes by pruning suboptimal branches
  • ✅ Handles 0/1 item selection
  • ✅ Useful for combinatorial optimization
  • ❌ Can be exponential without effective pruning

🔍 Step-by-Step Branch and Bound Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input items
2. Sort by value/weight ratio
3. Explore decision tree
4. Display result

Current Items (Sorted):

Algorithm State:

Node ID Level Profit Weight Bound Action

Decision Tree:

🎮 Practice Knapsack with Branch and Bound

Enter inputs, then click "Compute Max Value"

Test Cases

Example 1: u=2, v=10, weights=[5,5], values=[50,60] → 110.00

Example 2: u=3, v=6, weights=[1,1,3], values=[10,20,40] → 70.00

📊 Algorithm Analysis

Branch and Bound Process

  1. Sort Items: By value-to-weight ratio in descending order
  2. Initialize: Start with root node (level=-1, profit=0, weight=0)
  3. Explore Nodes: For each node, create branches for including/excluding the next item, compute bound, and prune if bound ≤ maxProfit
  4. Output: Maximum profit, rounded to two decimal places

Time Complexity

O(2^u)

Worst case, reduced by pruning

Space Complexity

O(u)

For queue and recursion stack

Key Points

  • Branch and Bound: Optimizes by pruning suboptimal branches
  • Bound Function: Estimates maximum possible profit
  • Applications: Resource allocation, scheduling
  • Limitation: Exponential time in worst case